SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Generalized assignment problem</title>

</head>

Generalized assignment problem

</h1>

</header>

In <a href="Applied_mathematics" title="Applied mathematics">applied mathematics</a>, the maximum generalized assignment problem is a problem in <a href="Combinatorial_optimization" title="Combinatorial optimization">combinatorial optimization</a>. This problem is a <a href="Generalization" title="Generalization">generalization</a> of the <a href="Assignment_problem" title="Assignment problem">assignment problem</a> in which both tasks and <a href="Agent-based_model" title="Agent-based model">agents</a> have a size. Moreover, the size of each task might vary from one agent to the other.

This problem in its most general form is as follows: There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost and profit that may vary depending on the agent-task assignment. Moreover, each agent has a budget and the sum of the costs of tasks assigned to it cannot exceed this budget. It is required to find an assignment in which all agents do not exceed their budget and total profit of the assignment is maximized.

<div class="mw-heading mw-heading2"><h2 id="In_special_cases">In special cases</h2></div>

In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the <a href="Assignment_problem" title="Assignment problem">assignment problem</a>. When the costs and profits of all tasks do not vary between different agents, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the <a href="Knapsack_problem" title="Knapsack problem">knapsack problem</a>.

<div class="mw-heading mw-heading2"><h2 id="Explanation_of_definition">Explanation of definition</h2></div>

In the following, we have n kinds of items, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1}}</annotation>

</semantics>

</math><img src="./bbf42ecda092975c9c69dae84e16182ba5fe2e07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.284ex; height:2.009ex;" alt="{\displaystyle a_{1}}" loading="lazy"> through <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{n}}</annotation>

</semantics>

</math><img src="./790f9209748c2dca7ed7b81932c37c02af1dbc31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.448ex; height:2.009ex;" alt="{\displaystyle a_{n}}" loading="lazy"> and m kinds of bins <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{1}}</annotation>

</semantics>

</math><img src="./9af2720c91be489f57ecde4bb651b95e113d0144.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.052ex; height:2.509ex;" alt="{\displaystyle b_{1}}" loading="lazy"> through <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{m}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{m}}</annotation>

</semantics>

</math><img src="./330e36691c8285b9c890d82a7c11855f3259dd58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.673ex; height:2.509ex;" alt="{\displaystyle b_{m}}" loading="lazy">. Each bin <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}}</annotation>

</semantics>

</math><img src="./40a8c2db2990a53c683e75961826167c5adac7c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.797ex; height:2.509ex;" alt="{\displaystyle b_{i}}" loading="lazy"> is associated with a budget <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t_{i}}</annotation>

</semantics>

</math><img src="./8b61e3d4d909be4a19c9a554a301684232f59e5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.639ex; height:2.343ex;" alt="{\displaystyle t_{i}}" loading="lazy">. For a bin <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}}</annotation>

</semantics>

</math><img src="./40a8c2db2990a53c683e75961826167c5adac7c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.797ex; height:2.509ex;" alt="{\displaystyle b_{i}}" loading="lazy">, each item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{j}}</annotation>

</semantics>

</math><img src="./d0096fb78d6843c9fb67a840dc796b61ad93eec2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.14ex; height:2.343ex;" alt="{\displaystyle a_{j}}" loading="lazy"> has a profit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{ij}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{ij}}</annotation>

</semantics>

</math><img src="./ca46e6d560ac4e615adcd6d053cd476f4aadfcbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:2.736ex; height:2.343ex;" alt="{\displaystyle p_{ij}}" loading="lazy"> and a weight <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{ij}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{ij}}</annotation>

</semantics>

</math><img src="./d3302ff355269436b43bc2fbe180303881c09321.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.141ex; height:2.343ex;" alt="{\displaystyle w_{ij}}" loading="lazy">. A solution is an assignment from items to bins. A feasible solution is a solution in which for each bin <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}}</annotation>

</semantics>

</math><img src="./40a8c2db2990a53c683e75961826167c5adac7c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.797ex; height:2.509ex;" alt="{\displaystyle b_{i}}" loading="lazy"> the total weight of assigned items is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t_{i}}</annotation>

</semantics>

</math><img src="./8b61e3d4d909be4a19c9a554a301684232f59e5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.639ex; height:2.343ex;" alt="{\displaystyle t_{i}}" loading="lazy">. The solution's profit is the sum of profits for each item-bin assignment. The goal is to find a maximum profit feasible solution.

Mathematically the generalized assignment problem can be formulated as an <a href="Integer_programming" title="Integer programming">integer program</a>:

<mtr>

<mtd>

<mtext>maximize </mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to </mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{maximize }}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}}</annotation>

</semantics>

</math><img src="./395a8c11e6e81d1eec7a130530a903fccf6835e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -11.678ex; margin-bottom: -0.327ex; width:58.7ex; height:25.176ex;" alt="{\displaystyle {\begin{aligned}{\text{maximize }}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Complexity">Complexity</h2></div>

The generalized assignment problem is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>.<a href="#cite_note-1">[1]</a> However, there are linear-programming relaxations which give a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1-1/e)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-1/e)}</annotation>

</semantics>

</math><img src="./d60bec91d88fd0dda9c72adb869b82e2f967cf07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.221ex; height:2.843ex;" alt="{\displaystyle (1-1/e)}" loading="lazy">-approximation.<a href="#cite_note-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Greedy_approximation_algorithm">Greedy approximation algorithm</h2></div>

For the problem variant in which not every item must be assigned to a bin, there is a family of algorithms for solving the GAP by using a combinatorial translation of any algorithm for the knapsack problem into an approximation algorithm for the GAP.<a href="#cite_note-3">[3]</a>

Using any <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy">-approximation algorithm ALG for the <a href="Knapsack_problem" title="Knapsack problem">knapsack problem</a>, it is possible to construct a (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha +1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha +1}</annotation>

</semantics>

</math><img src="./c8de281682e16a35de79915ddc9e3582d215e0ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.49ex; height:2.343ex;" alt="{\displaystyle \alpha +1}" loading="lazy">)-approximation for the generalized assignment problem in a greedy manner using a residual profit concept.

The algorithm constructs a schedule in iterations, where during iteration <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> a tentative selection of items to bin <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{j}}</annotation>

</semantics>

</math><img src="./fa56eff4488494085785b7b0d6e2069bd45a3ce5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.907ex; height:2.843ex;" alt="{\displaystyle b_{j}}" loading="lazy"> is selected.

The selection for bin <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{j}}</annotation>

</semantics>

</math><img src="./fa56eff4488494085785b7b0d6e2069bd45a3ce5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.907ex; height:2.843ex;" alt="{\displaystyle b_{j}}" loading="lazy"> might change as items might be reselected in a later iteration for other bins.

The residual profit of an item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> for bin <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{j}}</annotation>

</semantics>

</math><img src="./fa56eff4488494085785b7b0d6e2069bd45a3ce5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.907ex; height:2.843ex;" alt="{\displaystyle b_{j}}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{ij}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{ij}}</annotation>

</semantics>

</math><img src="./ca46e6d560ac4e615adcd6d053cd476f4aadfcbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:2.736ex; height:2.343ex;" alt="{\displaystyle p_{ij}}" loading="lazy"> if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> is not selected for any other bin or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{ij}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{ij}}</annotation>

</semantics>

</math><img src="./ca46e6d560ac4e615adcd6d053cd476f4aadfcbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:2.736ex; height:2.343ex;" alt="{\displaystyle p_{ij}}" loading="lazy"> – <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{ik}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{ik}}</annotation>

</semantics>

</math><img src="./c51b9deb2a2272d50cc2f1eb0519947e295607d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.915ex; height:2.009ex;" alt="{\displaystyle p_{ik}}" loading="lazy"> if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> is selected for bin <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{k}}</annotation>

</semantics>

</math><img src="./9ca33a19a52bbe58090767bcfb0aae551c925dcb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.086ex; height:2.509ex;" alt="{\displaystyle b_{k}}" loading="lazy">.

Formally: We use a vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> to indicate the tentative schedule during the algorithm. Specifically, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T[i]=j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T[i]=j}</annotation>

</semantics>

</math><img src="./ecf70352d15a33bd071eacbbaa335cab3c445f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.789ex; height:2.843ex;" alt="{\displaystyle T[i]=j}" loading="lazy"> means the item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> is scheduled on bin <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{j}}</annotation>

</semantics>

</math><img src="./fa56eff4488494085785b7b0d6e2069bd45a3ce5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.907ex; height:2.843ex;" alt="{\displaystyle b_{j}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T[i]=-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T[i]=-1}</annotation>

</semantics>

</math><img src="./3801d56543a44698441a22c570ac2586f74a076a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.801ex; height:2.843ex;" alt="{\displaystyle T[i]=-1}" loading="lazy"> means that item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> is not scheduled. The residual profit in iteration <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{j}}</annotation>

</semantics>

</math><img src="./4a5da6c3564a2129f714ef11acd8ba649d18e604.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.402ex; height:2.843ex;" alt="{\displaystyle P_{j}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{j}[i]=p_{ij}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{j}[i]=p_{ij}}</annotation>

</semantics>

</math><img src="./6b71b072bfa5f1923fe8a3dd9b3c1e909305e0af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.243ex; height:3.009ex;" alt="{\displaystyle P_{j}[i]=p_{ij}}" loading="lazy"> if item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> is not scheduled (i.e. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T[i]=-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T[i]=-1}</annotation>

</semantics>

</math><img src="./3801d56543a44698441a22c570ac2586f74a076a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.801ex; height:2.843ex;" alt="{\displaystyle T[i]=-1}" loading="lazy">) and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{j}[i]=p_{ij}-p_{ik}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{j}[i]=p_{ij}-p_{ik}}</annotation>

</semantics>

</math><img src="./3c20c409d3e4904d6184d8125e48a142ed9e319c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.909ex; height:3.009ex;" alt="{\displaystyle P_{j}[i]=p_{ij}-p_{ik}}" loading="lazy"> if item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> is scheduled on bin <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{k}}</annotation>

</semantics>

</math><img src="./9ca33a19a52bbe58090767bcfb0aae551c925dcb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.086ex; height:2.509ex;" alt="{\displaystyle b_{k}}" loading="lazy"> (i.e. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T[i]=k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T[i]=k}</annotation>

</semantics>

</math><img src="./aa5e72ae4c03b149d61bc04280960fcb91fb716b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.042ex; height:2.843ex;" alt="{\displaystyle T[i]=k}" loading="lazy">).

Formally:

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T[i]=-1{\text{ for }}i=1\ldots n}</annotation>

</semantics>

</math><img src="./4d7c83f8450a5e56ac92cc3f12c26435efad953e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.704ex; height:2.843ex;" alt="{\displaystyle T[i]=-1{\text{ for }}i=1\ldots n}" loading="lazy"></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=1,\ldots ,m}</annotation>

</semantics>

</math><img src="./745ead100813850e9d68e2a6cb6be14124998279.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:12.464ex; height:2.509ex;" alt="{\displaystyle j=1,\ldots ,m}" loading="lazy"> do:

<dl><dd>Call ALG to find a solution to bin <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{j}}</annotation>

</semantics>

</math><img src="./fa56eff4488494085785b7b0d6e2069bd45a3ce5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.907ex; height:2.843ex;" alt="{\displaystyle b_{j}}" loading="lazy"> using the residual profit function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{j}}</annotation>

</semantics>

</math><img src="./4a5da6c3564a2129f714ef11acd8ba649d18e604.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.402ex; height:2.843ex;" alt="{\displaystyle P_{j}}" loading="lazy">. Denote the selected items by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{j}}</annotation>

</semantics>

</math><img src="./222db49df2eefdb67737ba2d2dbd221a1bae0bf0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.335ex; height:2.843ex;" alt="{\displaystyle S_{j}}" loading="lazy">.</dd>

<dd>Update <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> using <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{j}}</annotation>

</semantics>

</math><img src="./222db49df2eefdb67737ba2d2dbd221a1bae0bf0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.335ex; height:2.843ex;" alt="{\displaystyle S_{j}}" loading="lazy">, i.e., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T[i]=j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T[i]=j}</annotation>

</semantics>

</math><img src="./ecf70352d15a33bd071eacbbaa335cab3c445f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.789ex; height:2.843ex;" alt="{\displaystyle T[i]=j}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in S_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in S_{j}}</annotation>

</semantics>

</math><img src="./b93fd5c04cb4159d077bc8d2c3b3f6dc83b60f3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.978ex; height:2.843ex;" alt="{\displaystyle i\in S_{j}}" loading="lazy">.</dd></dl></dd></dl>

<ul><li><a href="Assignment_problem" title="Assignment problem">Assignment problem</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFÖzbakirBaykasoğluTapkan2010" class="citation cs2">Özbakir, Lale; Baykasoğlu, Adil; Tapkan, Pınar (2010), Bees algorithm for generalized assignment problem, Applied Mathematics and Computation, vol. 215, Elsevier, pp. 3782–3795, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.amc.2009.11.018">10.1016/j.amc.2009.11.018</a></cite>.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFFleischerGoemansMirrokniSviridenko2006" class="citation conference cs1">Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim (2006). Tight approximation algorithms for maximum general assignment problems. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. pp. 611–620.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFCohenKatzirRaz2006" class="citation journal cs1">Cohen, Reuven; Katzir, Liran; Raz, Danny (2006). "An efficient approximation for the Generalized Assignment Problem". Information Processing Letters. 100 (4): 162–166. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.159.1947">10.1.1.159.1947</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ipl.2006.06.003">10.1016/j.ipl.2006.06.003</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFKellererPferschyPisinger2013" class="citation book cs1">Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2013-03-19). Knapsack Problems. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-24777-7</bdi>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-10-03" href="https://en.wikipedia.org/wiki/?title=Generalized_assignment_problem&oldid=1249232303">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>